


public class Day4 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    // K个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        // 先计算有几对需要进行翻转
        int n = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            n++;
        }
        n /= k;
        // 这个时候 n 就是需要处理的对数
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        cur = head;
        for(int i = 0;i < n;i++) {
            // 每次的cur就是要翻转的第一个节点
            ListNode tmp = cur; // 记录每次我们翻转前的第一个节点，翻转之后这个节点就是下次开始的位置，也就是往这个节点后面进行头插
            for(int j = 0;j < k;j++) {
                ListNode next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
                cur = next;
            }
            // 翻转完一对
            prev = tmp;
        }

        // 能翻转的对数都翻转结束，我们把不能翻转的直接放入到 翻转完的链表的后面
        prev.next = cur;
        return ret.next;
    }
}
